Graphs having dense data are frequently found in engineering fields including stereographic 3D and computer animation. However, since a graph having unnecessary dense data makes interactive control difficult, its simplifying methods have been developed.
For example, computer programs widely propagated and used at present provide a graph simplification function, called “simplify curve”. However, this curve simplification function does not properly extract salient points of an original graph. Thus, the curve simplified by the curve simplification function may not exactly express features of the original graph.
The Douglas-Peucker algorithm is a well-known algorithm for reducing the number of points in a curve that is approximated by a series of points. The Douglas-Peucker algorithm uses the greedy method that incrementally adds data that should be included in a graph, while remaining a starting point and an ending point on the graph. The Douglas-Peucker algorithm is known to give a generally good simplified graph, but this method is not able to extract an optimized simplified graph.